/*
 * @Description: 
 * @Version: 2.0
 * @Autor: wangmiao
 * @Date: 2022-11-08 14:18:41
 * @LastEditors: wangmiao
 * @LastEditTime: 2022-11-09 11:28:23
 */


// 创建节点
class Node{
  constructor(value) {
    this.val = value
    this.left = null
    this.right = null
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null
  }

  // 插入方法
  insert(value) {
    if(!this.root) {  // root为null，代表第一次插入
      this.root = new Node(value)
    }else {
      this.insertNode(this.root, value)
    }
  }
  insertNode(node, value) {
    if(value < node.val) {
      if(node.left === null) {
        node.left = new Node(value)
      } else {
        this.insertNode(node.left, value) // 如果节点的左子树不为null，则需要递归节点的左子树
      }
    }else {
      if(node.val < value) {
        if(node.right === null) {
          node.right = new Node(value)
        }else {
          this.insertNode(node.right, value)  // 如果节点的右子树不为null，则需要递归节点的右子树
        }
      }
    }
    
  }

  // 先序遍历
  preOrderTraverse(result) {
    this.preOrderTraverseNode(this.root, result)
    return result
  }
  preOrderTraverseNode(node, result) {
    if(!node) return
    result.push(node)
    this.preOrderTraverseNode(node.left, result)
    this.preOrderTraverseNode(node.right, result)
  }

  // 中序遍历
  inOrderTraverse(result) {
    this.inOrderTraverseNode(this.root, result)
    return result
  }
  inOrderTraverseNode(node, result) {
    if(!node) return
    this.inOrderTraverseNode(node.left, result)
    result.push(node)
    this.inOrderTraverseNode(node.right, result)
  }

  // 后序遍历
  postOrderTraverse(result) {
    this.postOrderTraverseNode(this.root, result)
    return result
  }
  postOrderTraverseNode(node, result) {
    if(!node) return
    this.postOrderTraverseNode(node.left, result)
    this.postOrderTraverseNode(node.right, result)
    result.push(node)
  }

  // 最小值
  min() {
    return this.minNode(this.root)
  }
  minNode(node) {
    let currentNode = node
    while(currentNode && currentNode.left) { // 找到最左边的节点
      currentNode = currentNode.left
    }
    return currentNode
  }

  // 最大值
  max() {
    return this.maxNode(this.root)
  }
  maxNode(node) {
    let currentNode = node
    while(currentNode && currentNode.right) {  // 找到最右边的节点
      currentNode = currentNode.right
    }
    return currentNode
  }

  // 查询某个特定值是否存在
  search(value) {
    return this.searchNode(this.root, value)
  }
  searchNode(node, value) {
    if(!node) return false
    if(node.val < value) {
      return this.searchNode(node.right, value)
    }else if(node.val > value) {
      return this.searchNode(node.left, value)
    }else {
      return true
    }
  }

  // 删除某个节点
  remove(value) {
    this.root = this.removeNode(this.root, value)
    return this.root
  }
  removeNode(node, value) {
    if(!node) return false
    if(value < node.val) {
      node.left = this.removeNode(node.left, value)
      return node
    }else if(value > node.val) {
      node.right = this.removeNode(node.right, value)
      return node
    }else {
      // 当找到所要删除的节点之后，分情况删除

      if(!node.left && !node.right) {  // 情况一： 删除的节点左右子树都为null，直接删除该节点
        node = null
        return node
      }else if(!node.left) {  // 情况二： 删除的节点只有一个右子树，需要把该节点右子树替换该节点
        node = node.right
        return node
      }else if(!node.right) {  // 情况二： 删除的节点只有一个左子树，需要把该节点左子树替换该节点
        node = left
        return node
      }else {  // 情况三： 删除的节点拥有左子树和右子树，我们需要找到其右子树中最小的节点替换该节点
        const rightMinNode = this.minNode(node.right)
        node.val = rightMinNode.val
        node.right = this.removeNode(node.right, rightMinNode.val)  // 删除右侧最小的节点
        return node
      }
    }
  }
  
}
let bstNode = new BinarySearchTree()
bstNode.insert(3)
bstNode.insert(4)
bstNode.insert(5)
bstNode.insert(2)
bstNode.insert(9)
bstNode.insert(8)
console.log(bstNode.remove(8))